// function lengthOfLIS(nums) {
//     const n = nums.length;
//     if (n === 0) return 0;
//     const dp = new Array(n).fill(1); // 初始化为1，每个元素自身构成子序列
//     let maxLen = 1;
//     for (let i = 1; i < n; i++) {
//         for (let j = 0; j < i; j++) {
//             if (nums[i] > nums[j]) {
//                 dp[i] = Math.max(dp[i], dp[j] + 1);
//             }
//         }
//         maxLen = Math.max(maxLen, dp[i]);
//     }
//
//     return maxLen;
// }

function lengthOfLIS(nums) {
    // tails 数组用于存储当前的最小末尾元素
    // tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
    const tails = [];

    // 遍历输入数组中的每个元素
    for (const num of nums) {
        // 使用二分查找在 tails 数组中找到 num 的插入位置
        let left = 0,
            right = tails.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 如果 left 等于 tails 的长度，说明 num 比 tails 中的所有元素都大
        // 可以将 num 添加到 tails 数组的末尾，表示找到了一个更长的递增子序列
        if (left === tails.length) {
            tails.push(num);
        } else {
            // 否则，用 num 替换 tails[left]，因为 num 可以作为更小的末尾元素
            // 这样可以确保 tails 数组中的元素尽可能小，为后续的递增子序列提供更多可能性
            tails[left] = num;
        }
    }

    // tails 的长度就是最长递增子序列的长度
    return tails.length;
}

